Robert Marks on the math paradox challenging physics
| December 15, 2015 | Posted by News under Information |
Yesterday
we noted new findings that a math paradox might make physics problems
unanswerable be unanswerable (and thus maybe turn the physics problems
into paradoxes too).
Robert Marks II, computer science prof at Baylor U and editor-in-chief of Bio-Complexity , offers some thoughts:
Anything algorithmic can be done by a computer. Give me a recipe for doing something, and I can whip it up in the kitchen. There are things which are not algorithmic the most celebrated of which is Turing’s halting problem: there exists no algorithm able tell whether or not a computer program runs forever or halts. (The halting algorithm must work for any and all computer programs.)
But a computer program will halt or won’t halt. But since there is no algorithm to figure this out, the halting problem is undecidable. We don’t know before running the program whether or not it will halt. It could run trillions of years and then halt long after we’re dead. If it doesn’t halt, we may never know (unless we know the so-called busy beaver numbers which is the same as knowing Chaitin’s number which is unknowable. But I digress.)
I’ve always thought this is a strong statement about determinism. A computer program that doesn’t use randomness is deterministic. There it is. All 12,465 lines of code. Yet we don’t know whether or not this deterministic program will halt or not. Rice’s Theorem extends undecidability to any “non-trivial” property of the computer program. We can’t even write an algorithm to tell us whether or not the number 3 will be printed by a computer program! So undecidability is much greater than only the problem of halting.
Chaitin wrote a book called The Unknowable that addressed this view of undecidability. (His other books are better.) Chaitin’s number is a single number between 0 and 1 that, if known, would allow solution of ALL the unsolved problems in math that can be resolved with a single counterexample (assuming we had gobs of time and computer memory.) Its construction uses the halting problem. So the C++ on your computer has a deterministic Chaitin’s number. But it is unknowable. Bummer.
Lastly, Roger Penrose in Shadows of the Mind and The Emperor’s New Mind makes the case the human mind, through creativity and the creation of information, does nonalgorithmic things (and is therefore not merely a computer).
I am starting to believe creation of information requires a nonalgorithmic process, hence intelligent design.
Creation of information as a nonalgorithmic process? Most writers you’d ever want to read would understand that. See also: How DOES creativity happen? Have we found the answer via neuroscience?
The
creation of new information is not incomprehensible. But it often
cannot be understood in the way many insist on trying to understand it.
On the other hand, their attempts do often generate suitable subjects of
fun.
See also: Math problems unanswerable due to physics paradox? Or versa vice? Early overheard comments say that the issue turns on undecidability and could have big implications for naturalism.
Follow UD News at Twitter!
5 Responses to Robert Marks on the math paradox challenging physics
Leave a Reply
You must be logged in to post a comment.
Both this post and the discussion of the physics result seem to skipp this point
There are plenty of programs that can be shown to halt or not. The halting problem only tells us that it’s not possible to generate a general solution. Likewise (as I understand it) the physics results tells there is no general solution that will allow us to predict arbitrarily small spectral gaps. That doesn’t mean specific solutions can’t be found.
Furthermore, the undecidability result only applies to an infinite lattice. From the Nature article:
Unsurprisingly, this is similar to the underlying halting problem: the question of whether a given program halts within N steps is computable. The halting problem only becomes undecidable if you remove the limit and ask whether it halts given infinite time.
Essentially, you can’t always answer infinite questions in a finite computation. Looked at this way, it’s not really surprising, and it’s hard to see why it would have any particular metaphysical implications.
Although I do not know about the details of the halting problem in particular, I do know that Godel’s incompleteness theorem does have some fairly profound ‘metaphysical implications’ overall.
As to the implications of his incompleteness theorem:
Notes as to how Godel’s work relates to ID
Verse and Music:
Bornagain @3
Turnings halting problem is a basic reformulation of Godel’s incompleteness theorems. Essentially, any algorithm is nothing more than a formal mathematical system so the ideas are the same. Roger Penrose also gives his own version in Shadows Of The Mind.
OT
Hello aqeels,
I haven’t seen you here in a while. I hope you’ve had a chance to visit my project pages.
http://www.Biosemiosis.org
http://www.ComplexityCafe.com
best regards…